#include "tree.h"

    // PNG *p; //the upper left pixel
    // Node **children; //pointer to four other node
    // int width; //当前像素区块的宽度
    // int height; //当前像素区块的高度
    // bool leaf; //是否是叶子节点，true 代表是叶子节点
    // int x; //当前像素区块左上角顶点像素的横坐标
    // int y; //当前像素区块左上角顶点像素的纵坐标
    // int mean_r; //Rmean
    // int mean_g; //Gmean
    // int mean_b; //Bmean

Node::Node() {
    //TODO
    //Node的构造函数。每一个 Node 代表了一个图片区块，你需要初始化相关变量。
    this->width=0;
    this->height=0;
    this->leaf=true;//默认为叶子节点，当创建后代时，改为false
    this->x=0;
    this->y=0;
    this->mean_b=0;
    this->mean_g=0;
    this->mean_r=0;
    this->p=NULL;
    this->children=new Node*[4];
    cut_count=0;
    cut_flag=false;

}

Node::Node(PNG* corner, int input_width, int input_height, int x, int y) {
    //TODO
    //构建一个管辖图片区块的Node。x，y表示区块左上角的坐标，input_width和input_height表示区块的尺寸。
    this->width=input_width;
    this->height=input_height;
    if(input_width==1&&input_height==1)
    this->leaf=true;//如果宽高都为1,则是叶子节点
    else this->leaf=false;
    this->x=x;
    this->y=y;
    this->mean_b=0;
    this->mean_g=0;
    this->mean_r=0;
    this->p=corner;
    this->children=new Node*[4];
    cut_count=0;
    cut_flag=false;

}

Node::Node(Node &other) {
    //TODO
    //拷贝 Node 对象的拷贝构造函数。
    this->width=other.width;
    this->height=other.height;
    this->leaf=other.leaf;
    this->x=other.x;
    this->y=other.y;
    this->mean_b=other.mean_b;
    this->mean_g=other.mean_g;
    this->mean_r=other.mean_r;
    *(this->p)=*(other.p);
    children=new Node*[4];
    *children[0]=*(other.children[0]);
    *children[1]=*(other.children[1]);
    *children[2]=*(other.children[2]);
    *children[3]=*(other.children[3]);
    cut_count=other.cut_count;
}

Node::Node(Node &&other) {
    //TODO
    //拷贝 Node 对象的拷贝构造函数（右值）
    this->width=other.width;
    this->height=other.height;
    this->leaf=other.leaf;
    this->x=other.x;
    this->y=other.y;
    this->mean_b=other.mean_b;
    this->mean_g=other.mean_g;
    this->mean_r=other.mean_r;
    *(this->p)=*(other.p);
    children=new Node*[4];
    *children[0]=*(other.children[0]);
    *children[1]=*(other.children[1]);
    *children[2]=*(other.children[2]);
    *children[3]=*(other.children[3]);
    other.children=NULL;
    other.p=NULL;
    cut_count=other.cut_count;
}

Node& Node::operator=(Node &other) {
    //TODO
    //和拷贝构造函数类似的等号赋值操作符。
    this->width=other.width;
    this->height=other.height;
    this->leaf=other.leaf;
    this->x=other.x;
    this->y=other.y;
    this->mean_b=other.mean_b;
    this->mean_g=other.mean_g;
    this->mean_r=other.mean_r;
    *(this->p)=*(other.p);
    children=new Node*[4];
    *children[0]=*(other.children[0]);
    *children[1]=*(other.children[1]);
    *children[2]=*(other.children[2]);
    *children[3]=*(other.children[3]);
    cut_count=other.cut_count;
    return *this;
}

Node& Node::operator=(Node &&other) {
    //TODO
    //和拷贝构造函数类似的等号赋值操作符（右值）。
    this->width=other.width;
    this->height=other.height;
    this->leaf=other.leaf;
    this->x=other.x;
    this->y=other.y;
    this->mean_b=other.mean_b;
    this->mean_g=other.mean_g;
    this->mean_r=other.mean_r;
    *(this->p)=*(other.p);
    children=new Node*[4];
    *children[0]=*(other.children[0]);
    *children[1]=*(other.children[1]);
    *children[2]=*(other.children[2]);
    *children[3]=*(other.children[3]);
    other.children=NULL;
    other.p=NULL;
    return *this;
}

int Node::get_height()
{
    return height;
}

int Node::get_width()
{
    return width;
}

PNG* Node::get_png()
{
    return this->p;
}

void Node::set_color(uint8_t r,uint8_t g,uint8_t b)
{
    mean_r=r;
    mean_g=g;
    mean_b=b;
}

color_inf Node::get_color()
{
    color_inf cf;
    cf.r=this->mean_r;
    cf.g=this->mean_g;
    cf.b=this->mean_b;
    return cf;
}

bool Tree::check_cut_count(Node* this_node)
{
    if(this_node==NULL)return true;
    if(this_node->cut_count>2)
    {
        return false;
    }
    return(
    check_cut_count(this_node->get_children()[0])
    &&check_cut_count(this_node->get_children()[1])
    &&check_cut_count(this_node->get_children()[2])
    &&check_cut_count(this_node->get_children()[3]));

}

std::vector<Node*> Tree::get_children_list(Node* this_root)
{
    std::vector<Node*>v;
    if(this_root->get_children()[0]==NULL);
    else v.push_back(this_root->get_children()[0]);
    if(this_root->get_children()[1]==NULL);
    else v.push_back(this_root->get_children()[1]);
    if(this_root->get_children()[2]==NULL);
    else v.push_back(this_root->get_children()[2]);
    if(this_root->get_children()[3]==NULL);
    else v.push_back(this_root->get_children()[3]);
    return v;
}

int Node::get_x()
{
    return x;
}

int Node::get_y()
{
    return y;
}

void Tree::judge(int threshold) {
    //TODO
    //我们需要针对你在上一个部分制作的树状数据结构进行类似“剪枝”的操作（这里其实不是剪枝）。
    //如果一个节点的所有叶子节点被判定为类似，你可以放弃所有叶子节点的信息
    //（也就是将区块内所有叶子像素的红、绿、蓝、阿尔法值设为一个平均值）。
    
    //递归改变节点颜色（对需要cut的），暂存于node中
    DFS(root,threshold);

    //根据最后的叶子节点数据更新pxls
    // for(int i=0;i<leaf.size();i++)
    // {
    //     leaf[i]->set_color_to_pxls(orgin_png,leaf[i]->get_color().r,leaf[i]->get_color().g,leaf[i]->get_color().b,orgin_png->get_width()*leaf[i]->get_y()+leaf[i]->get_x());
    // }

}

void Tree::DFS(Node* this_root,int threshold)
{//后续遍历查找需要cut的

    if(this_root==NULL)return;
    std::vector<Node*>children_list=get_children_list(this_root);
    if(children_list.size()==0)return;
    
    DFS(this_root->get_children()[0],threshold);
    DFS(this_root->get_children()[1],threshold);
    DFS(this_root->get_children()[2],threshold);
    DFS(this_root->get_children()[3],threshold);

    uint8_t r_av,g_av,b_av;
    
    //获取平均颜色，就保存在node中
    r_av=this_root->get_color().r;
    g_av=this_root->get_color().g;
    b_av=this_root->get_color().b;
    //计算方差var
    int sum_r=0,sum_g=0,sum_b=0;
    for(int i=0;i<children_list.size();i++)
    {
        sum_r+=(int(r_av)-children_list[i]->get_color().r)*(int(r_av)-children_list[i]->get_color().r);
        sum_g+=(int(g_av)-children_list[i]->get_color().g)*(int(g_av)-children_list[i]->get_color().g);
        sum_b+=(int(b_av)-children_list[i]->get_color().b)*(int(b_av)-children_list[i]->get_color().b);
    }
    int var=(sum_b+sum_g+sum_r)/(30*children_list.size());
    if(var<threshold)
    {
        cut(this_root,r_av,g_av,b_av);
    }


}

void Node::set_color_to_pxls(PNG* origin_png,uint8_t r,uint8_t g,uint8_t b,int i)
{
    pxl* image_list=origin_png->get_image_pxls();
    image_list[i].blue=b;
    image_list[i].green=g;
    image_list[i].red=r;
    return;
}

void Tree::cut(Node* this_node,uint8_t r,uint8_t g,uint8_t b)
{
    if(this_node==NULL)return;
    if(!check_cut_count(this_node))return;
    if(this_node->get_height()==1&&this_node->get_width()==1)
    {
        //this_node->set_color(r,g,b);
        this_node->set_color_to_pxls(orgin_png,r,g,b,orgin_png->get_width()*this_node->get_y()+this_node->get_x());
    }
    this_node->cut_count++;
    this_node->cut_flag=true;
    cut(this_node->get_children()[0],r,g,b);
    cut(this_node->get_children()[1],r,g,b);
    cut(this_node->get_children()[2],r,g,b);
    cut(this_node->get_children()[3],r,g,b);
    
}

void Tree::create_tree(Node *this_node,PNG* png,int width,int height,int x,int y)
{
    if(this_node==NULL||width*height<1)return;
    if(width==1&&height==1)
    {
        uint8_t r= orgin_png->get_pxl(this_node->get_x(),this_node->get_y())->red;
        uint8_t g= orgin_png->get_pxl(this_node->get_x(),this_node->get_y())->green;
        uint8_t b= orgin_png->get_pxl(this_node->get_x(),this_node->get_y())->blue;
        this_node->set_color(r,g,b);
        this_node->get_children()[0]=NULL;
        this_node->get_children()[1]=NULL;
        this_node->get_children()[2]=NULL;
        this_node->get_children()[3]=NULL;
        return;
    }
    int width_middle=width/2-1;//算出左偏的宽度middle
    int height_middle=height/2-1;//算出上偏的高度middle值
    //封装四个角块进node
    Node* u_l_node=new Node(png,width_middle+1,height_middle+1,x,y);
    Node* u_r_node=new Node(png,width-(width_middle+1),height_middle+1,x+width_middle+1,y);
    Node* d_l_node=new Node(png,width_middle+1,height-(height_middle+1),x,y+height_middle+1);
    Node* d_r_node=new Node(png,width-(width_middle+1),height-(height_middle+1),x+width_middle+1,y+height_middle+1);
    //让他们成为后代
    if(u_l_node->get_height()>=1&&u_l_node->get_width()>=1)this_node->get_children()[0]=u_l_node;
    else this_node->get_children()[0]=NULL;
    if(u_r_node->get_height()>=1&&u_r_node->get_width()>=1)this_node->get_children()[1]=u_r_node;
    else this_node->get_children()[1]=NULL;
    if(d_l_node->get_height()>=1&&d_l_node->get_width()>=1)this_node->get_children()[2]=d_l_node;
    else this_node->get_children()[2]=NULL;
    if(d_r_node->get_height()>=1&&d_r_node->get_width()>=1)this_node->get_children()[3]=d_r_node;
    else this_node->get_children()[3]=NULL;

    //递归
    create_tree((this_node->get_children())[0],png,width_middle+1,height_middle+1,x,y);
    create_tree((this_node->get_children())[1],png,width-(width_middle+1),height_middle+1,x+width_middle+1,y);
    create_tree((this_node->get_children())[2],png,width_middle+1,height-(height_middle+1),x,y+height_middle+1);
    create_tree((this_node->get_children())[3],png,width-(width_middle+1),height-(height_middle+1),x+width_middle+1,y+height_middle+1);

}

void Tree::fresh_mean(Node *this_root)
{
    if(this_root==NULL)return;
    std::vector<Node*>children_list=get_children_list(this_root);
    if(children_list.size()==0)return;
    fresh_mean(this_root->get_children()[0]);
    fresh_mean(this_root->get_children()[1]);
    fresh_mean(this_root->get_children()[2]);
    fresh_mean(this_root->get_children()[3]);
    uint8_t r_av,g_av,b_av;
    int rp=0,gp=0,bp=0;
    for(int i=0;i<children_list.size();i++)
    {
        rp+=children_list[i]->get_color().r;
        gp+=children_list[i]->get_color().g;
        bp+=children_list[i]->get_color().b;
    }
    //计算的到孩子节点的颜色平均
    r_av=(uint8_t)(rp/children_list.size());
    g_av=(uint8_t)(gp/children_list.size());
    b_av=(uint8_t)(bp/children_list.size());
    this_root->set_color(r_av,g_av,b_av);

}


void Tree::load_png(PNG *png) {//png里的image含有大量像素点,也包含这个区块的宽高
    //TODO
    //读取PNG对象并建树。每一个节点都对应了图片上的一个像素区块，而叶子节点对应的是具体的像素。
    //每一个像素区块都有自己的长宽和位置，x，y表示区块左上角的坐标。
    //因为这是一个四叉树，原则上每个区块下分为四个子区块，但是有些边界条件可以不遵守这个约定。
    //采用十字分法
    //树在初始化时已经有root节点
    orgin_png=png;
    //根节点
    root=new Node(png,png->get_width(),png->get_height(),0,0);
    //建树
    create_tree(root,png,png->get_width(),png->get_height(),0,0);
    //后续遍历刷新所有节点的mean
    fresh_mean(root);
    
}



Node** Node::get_children()
{
    return children;
}


/*
 ================================================
 ====DO NOT MODIFY ANY OF THE FUNCTIONS BELOW====
 ==============请不要修改以下任何函数================
 ================================================
 */

Node::~Node() {
    for (int i = 0; i < 4; i++) 
    {
        if (children[i]!=NULL) 
        {
            delete children[i];
        }
    }
    delete[] children;
}

void Node::print() {
    if (children[0] != NULL) {
        children[0]->print();
    }
    if (children[1] != NULL) {
        children[1]->print();
    }
    if (children[2] != NULL) {
        children[2]->print();
    }
    if (children[3] != NULL) {
        children[3]->print();
    }
    printf("Red: %u, Green: %u, Blue: %u, Width: %d, Height: %d\n", mean_r, mean_g, mean_b, width, height);
    //printf("Red: %u, Green: %u, Blue: %u, Width: %d, Height: %d,", p->red, p->green, p->blue, width, height);
    std::cout << "Leaf: " << leaf << std::endl;
    return;
}

pxl* Node::get_pxl() {
    return p->get_pxl(x,y);
}

Tree::Tree() {
    root = new Node();
}

Tree::~Tree() {
    delete root;
}

Tree::Tree(Tree &other) {
    if (other.root != NULL) {
        root = new Node(*other.root);
    }
}

Tree& Tree::operator=(Tree &other) {
    if (other.root != NULL && &other != this) {
        root = new Node(*(other.root));
    }
    return *this;
}

pxl *Tree::get_pxl() {
    return root->get_pxl();
}

void Tree::print() {
    root->print();
}
